package 二三年8月;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 无重复字符的最长子串
 *
 *  给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 *
 *  思路：遍历字符串，用一个Set集合保存添加过的字符，两重循环连续遍历，如果重复了，就清空，对比下一个
 *
 */
public class L_03 {

    /**
     * 这样写的缺点是双层循环，时间复杂度O(n^2)
     *  而且不能满足“aab” ， ab的情况，会少算一位，所以需要优化
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        if(s == null){
             return 0;
        }
        if(s.length()<2){
            return s.length();
        }
        if(s.length() == 2 && s.charAt(0) != s.charAt(1)){
            return 2;
        }else if(s.length() == 2 && s.charAt(0) != s.charAt(1)){
            return 1;
        }
        int i,j;
        int max =0;
        Set<Character> set = new HashSet<>();
        for ( i = 0; i < s.length()-1 ; i++) {
            set.add(s.charAt(i));
            for ( j = i+1; j < s.length() ; j++) {
                // 然后添加最长子串
                // 包含就比较最大值，清空，跳出本次循环
                if(set.contains(s.charAt(j))){
                    max = Math.max(max,j-i);
                    set.clear();
                    break;
                }else {
                    set.add(s.charAt(j));
                }
            }
        }
        return max;
    }

    /**
     * 标准版， 滑动窗口的代码
     * 做一个滑动窗口的代码，存放字符串的位置
     * @param s
     * @return
     */
    public int lengthOfLongestSubstringToSure(String s) {
        if(s.length() == 0){
            return 0;
        }
        Map<Character,Integer> map =new HashMap<>();
        int max = 0;
        int left = 0;
        for (int i = 0; i < s.length() ; i++) {
             // 如果当前字符包含在滑动窗口内部，就改变left，以下一位当前字符为起点比较
            if(map.containsKey(s.charAt(i))){
                left = Math.max(left,map.get(s.charAt(i))+1);
            }
            // 用当前的字符值--下标保存， 遇到相同的用最新的替换
            map.put(s.charAt(i),i);
            max = Math.max(max,i-left+1);
        }
        return max;
    }

    public static void main(String[] args) {
        L_03 test = new L_03();
        String s = "au";
        test.lengthOfLongestSubstring(s);
    }
}
